package AVL;

public class AVLTree {
    class AvlTree{
        int val;
        AvlTree left;
        AvlTree right;
        AvlTree parent;
        int bf;
        public AvlTree(int val){
            this.val = val;
        }
    }

    AvlTree root = null;
    public boolean add(int val){
        if(root == null){
            root = new AvlTree(val);
            return true;
        }
        AvlTree parent = null;
        AvlTree cur = root;
        while(cur != null){//寻找插入位置
            parent = cur;
            if(val > cur.val){
                cur = cur.right;
            }else if (val == cur.val){
                return false;
            }else {
                cur = cur.left;
            }
        }
        AvlTree node = new AvlTree(val);

        if(parent.val > val){
            parent.left = node;
        }else {
            parent.right = node;
        }


        node.parent = parent;
        cur = node;
        //插入完成以后，调整平衡因子
        while (parent != null){
            if(cur == parent.left){
                parent.bf--;
            }else {
                parent.bf++;
            }
            if(parent.bf == 0){
                return true;
            }
            if(parent.bf == 2 || parent.bf == -2){
                if(parent.bf == -2){
                    if(cur.bf == -1){//右单旋
                        rightRevolve(cur);
                    }else if(cur.bf == 1){//左右双旋
                        leftRightRevolve(cur);
                    }else System.out.println("出错了 -2");

                }else {
                    if(cur.bf == 1){//左单旋
                        leftRevolve(cur);
                    }else if(cur.bf == -1){//右左双旋
                        rightLeftRevolve(cur);
                    }else System.out.println("出错了 +2");
                }
                return true;
            }

            cur = parent;
            parent = parent.parent;
        }
        return true;
    }
    //右左双旋
    private void rightLeftRevolve(AvlTree cur) {
        AvlTree p = cur.parent;
        AvlTree curL = cur.left;
        int bf = curL.bf;
        rightRevolve(cur.left);
        leftRevolve(curL);

        if(bf == -1){
            cur.bf = 1;
            p.bf = 0;
            curL.bf = 0;
        }else if(bf == 1){
            cur.bf = 0;
            p.bf = -1;
            curL.bf = 0;
        }

    }

    //左右双旋
    private void leftRightRevolve(AvlTree cur) {
        AvlTree p = cur.parent;
        AvlTree curR = cur.right;
        int bf = curR.bf;
        leftRevolve(cur.right);
        rightRevolve(curR);

        if(bf == 1){
            cur.bf = -1;
            p.bf = 0;
            curR.bf = 0;
        }else if (bf == -1){
            cur.bf = 0;
            p.bf = 1;
            curR.bf = 0;
        }

    }

    //左单旋
    private void leftRevolve(AvlTree cur) {
        AvlTree parent = cur.parent;
        AvlTree curL = cur.left;
        AvlTree pParent = parent.parent;

        parent.right = curL;
        if(curL != null){
            curL.parent = parent;
        }
        cur.left = parent;
        parent.parent = cur;
        cur.parent = pParent;
        if(pParent == null){
            root = cur;
        }else {
            if(pParent.left == parent){
                pParent.left = cur;
            }else {
                pParent.right = cur;
            }
        }

        cur.bf = 0;
        parent.bf = 0;
    }

    //右单旋
    private void rightRevolve(AvlTree cur) {
        AvlTree parent = cur.parent;
        AvlTree curR = cur.right;
        AvlTree parentP = parent.parent;

        parent.left = curR;
        if(curR != null){
            curR.parent = parent;
        }
        cur.right = parent;
        parent.parent = cur;
        cur.parent = parentP;

        if(parentP == null){
            root = cur;
        }else {
            if(parentP.right == parent){
                parentP.right = cur;
            }else {
                parentP.left = cur;
            }
        }

        cur.bf = 0;
        parent.bf = 0;
    }

    public Boolean isBalance(AvlTree head){
        if(head == null){
            return true;
        }
        int leftH = height(head.left);
        int rightH = height(head.right);
        if(head.bf != rightH - leftH){
            System.out.println("这个值位置bf: " + head.val +" 有问题!");
            return false;
        }
        return Math.abs(rightH - leftH) <= 1 && isBalance(head.left) && isBalance(head.right);
    }

   private int height(AvlTree head){
        if(head == null) {
            return 0;
        }
        int leftH = height(head.left) + 1;
        int rightH = height(head.right) + 1;
        return Math.max(rightH,leftH);
   }

   public void print(AvlTree head){
        if(root == null){
            System.out.println("null");
        }
        if(head == null){
            return;
        }
        print(head.left);
        System.out.print("val: " + head.val + " bf: " + head.bf + "  ");
        print(head.right);

   }

    public static void main(String[] args) {
        float a = 13;
        System.out.println(a/0);
    }
}